﻿#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//https://leetcode.cn/problems/3sum/description/

//void Swap(int* a, int* b)
//{
//	int tmp = *a;
//	*a = *b;
//	*b = tmp;
//}
//升序
//void InsertSort(int* a, int n)
//{
//	//[0,end] [end+1,n]
//	for (int i = 0; i < n -1; i++)
//	{
//		int end = i;
//		int tmp = a[end + 1];
//
//		while (end >= 0)
//		{
//			if (a[end] < tmp)
//			{
//				a[end + 1] = a[end];
//				end--;
//			}
//			else {
//				break;
//			}
//			a[end + 1] = tmp;
//		}
//	}
//}

class Solution
{
public:
	vector<vector<int>> threeSum(vector<int>& nums)
	{
		vector<vector<int>> ret;
		// 1. 排序
		sort(nums.begin(), nums.end());
		// 2. 利⽤双指针解决问题
		int n = nums.size();
		for (int i = 0; i < n; ) // 固定数 a
		{
			if (nums[i] > 0) break; // ⼩优化
			int left = i + 1, right = n - 1, target = -nums[i];
			while (left < right)
			{
				int sum = nums[left] + nums[right];
				if (sum > target) right--;
				else if (sum < target) left++;
				else
				{
					ret.push_back({ nums[i], nums[left], nums[right] });
					left++, right--;
					// 去重操作 left 和 right
					while (left < right && nums[left] == nums[left - 1]) left++;
					while (left < right && nums[right] == nums[right + 1])
						right--;									
				}
			}
			// 去重 i
			i++;
			while (i < n && nums[i] == nums[i - 1]) i++;
		}
		return ret;
	}
};

//
//int  main() {
//	int a[] = {-1,0,1,2,-1,-4};
//
//
//	return 0;
//}